package sort;

import java.util.Stack;

/**
 * 排序
 */
public class Sort {
    /**
     * 直接插入排序
     * 时间复杂度：最坏 O(n*2) 最好 O(n)
     * 空间复杂度: O(1)
     * 稳定性: 稳定
     * 优点：当数据越有序,排序越快 适用于待排序序列已经基本上趋于有序了
     * 缺点: 效率低
     * @param arr
     */
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if (arr[j] > tmp){//这里加不加等号和稳定有关系
                    // 但是:本身稳定的排序可以变为不稳定的排序,本身不稳定的排序不可以变成稳定的排序
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = tmp;

        }
    }

    public static void insertSort(int[] arr, int left, int right){
        for (int i = left+1; i <= right; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= left ; j--) {
                if (arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = tmp;

        }
    }


    /**
     * 希尔排序
     * 稳定性: 不稳定
     * 空间复杂度: O(1)
     * 时间复杂度: 不确定
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap = arr.length;
        while(gap > 1) {
            gap /= 2;
            shell(arr, gap);
        }
    }



    private static void shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {//交替排序
            int tmp = arr[i];
            int j = i-gap;
            for (; j >= 0 ; j-=gap) {
                if (arr[j] > tmp){
                    arr[j+gap] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap] = tmp;

        }

    }

    /**
     * 选择排序
     * 时间复杂度: O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     * @param arr
     */
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            int j = i + 1;//j为i的后一个下标
            for (; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]){
                    minIndex = j;//找到最小元素所在的下标
                }
            }
            //交换 i 和 minIndex 位置的元素
           if (i != minIndex){
               int tmp = arr[i];
               arr[i] = arr[minIndex];
               arr[minIndex] = tmp;
           }else{
               continue;
           }
        }
    }

    /**
     * 双向选择排序
     * 时间复杂度: O(n^2)
     * @param arr
     */
    public static void selectSort2(int[] arr){
        int left = 0;
        int right = arr.length-1;
        while(left < right){
            int minIndex = left,maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (arr[i] < arr[minIndex]){
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]){
                    maxIndex = i;
                }

            }
            swap(arr,minIndex,left);
            if(maxIndex == left){//以防第一个就是max值,如果和最小的一换,那最大值就跑到了最小值的位置
                maxIndex = minIndex;
            }
            swap(arr,maxIndex,right);
            left++;
            right--;



        }

    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    /**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     * @param arr
     */
    public static void heapSort(int[] arr){
        createHeap(arr);
        int end = arr.length - 1;
        while(end > 0){
            swap(arr,0,end);
            siftDown(arr,0,end);
            end--;
        }
    }

    /**
     * 向下调整
     * @param arr
     * @param parent
     * @param len
     */
    private static void siftDown(int[] arr, int parent, int len) {
        int child = 2*parent + 1;
        //至少有左孩子
        while(child < len){
            //左孩子 和 右孩子 比较大小
            if (child+1 < len && arr[child] < arr[child+1]){//child + 1 解决越界问题
                //保存两个孩子中较大的节点
                child = child + 1;
            }
            if (arr[child] > arr[parent]){
                // 交换
                swap(arr,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }


        }

    }

    /**
     * 创建大根堆
     * @param arr
     */
    private static void createHeap(int[] arr) {
        for (int parent = (arr.length-1-1)/2; parent >= 0 ; parent--) {
            siftDown(arr,parent,arr.length);

        }
    }

    /**
     * 冒泡排序
     * 时间复杂度: O(n^2)
     * 优化后最好情况可以达到 O(N)
     * 空间复杂度: O(1)
     * 稳定性: 稳定
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {//i代表趟数
            boolean flg = false;//如果没有发生交换那么下一次就不进入循环
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    flg = true;
                }
            }
            if (!flg){
                break;
            }
        }
    }

    /**
     * 快速排序
     * 时间复杂度:
     *          最好 O(N*logN)
     *          最坏 O(N^2) 逆序或有序
     * 空间复杂度:
     *          最好 O(logN)
     *          最坏 O(N) 逆序或有序
     * 稳定性: 不稳定
     * @param arr
     */
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);

    }

    /**
     * 求中位数的下标
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int middleNum(int[] arr, int left, int right){
        int mid = (left+right)/2;
        if (arr[left] < arr[right]){
            if (arr[mid] < arr[left]){
                return left;
            } else if (arr[mid] > arr[right]) {
                return right;
            } else {
                return mid;
            }
        }else{
            if (arr[mid] < arr[right]){
                return right;
            } else if (arr[mid] > arr[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    private static void quick(int[] arr, int start, int end){
        if (start >= end){
            return;
        }
        if (end - start + 1 <= 15){//优化1： 处理元素较少时直接使用插入排序
            insertSort(arr,start,end);
            return;
        }
        // 1 2 3 4 5 6 7
        int index = middleNum(arr,start,end);
        swap(arr,index,start);
        // 4 2 3 1 5 6 7 优化2： 降低树的高度
//        int pivot = partitionHoare(arr,start,end);
        int pivot = partitionHole(arr,start,end);
        quick(arr,start,pivot-1);
        quick(arr,pivot+1,end);

    }

    private static int partitionHoare(int[] arr, int left, int right) {
        int tmp = arr[left];
        int i = left;//要先记录
        while (left < right){
            //单独的循环 不能一直减到超过最左边的边界
            while (left < right && arr[right] >= tmp){
                right--;
            }
            while (left < right && arr[left] <= tmp){
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,i,left);
        return left;
    }

    /**
     * 挖坑法
     * 等号不能省,否则会有死循环
     * 如果先走左边,有可能会出现 相遇的是大的数据 最后把大的数据放在前面 就没有达到左边小右边大
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partitionHole(int[] arr, int left, int right){
        int tmp = arr[left];
        while (left < right){
            //单独的循环 不能一直减到超过最左边的边界
            while (left < right && arr[right] >= tmp){
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;//相遇时
        return left;
    }

    /**
     * 非递归快排
     * @param arr
     */
    public static void quickSortNor(int[] arr){
        int start = 0;
        int end = arr.length-1;
        Stack<Integer> stack = new Stack<>();
        int pivot = partitionHoare(arr,start,end);
        if(pivot-1 > start) {
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot+1 < end) {
            stack.push(pivot+1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partitionHoare(arr,start,end);
            if(pivot-1 > start) {
                stack.push(start);
                stack.push(pivot-1);
            }
            if(pivot+1 < end) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }

    }

    /**
     * 归并排序  (分治思想)
     * 时间复杂度: O(N*logN)
     * 空间复杂度: O(N) 树的高度
     * 稳定性: 稳定
     * 稳定的排序有: 直接插入排序 归并排序 冒泡排序
     * @param arr
     */
    public static void mergeSort(int[] arr){
        mergeSortFun(arr,0,arr.length-1);
    }

    private static void mergeSortFun(int[] arr, int start, int end){
        if(start >= end){
            return;
        }
        int mid = (start+end)/2;
        mergeSortFun(arr,start,mid);//左
        mergeSortFun(arr,mid+1,end);//右
        //合并
        merge(arr,start,mid,end);


    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //定义一个新的数组
        int[] tmpArr = new int[right-left+1];
        //同时满足说明两个归并段都有数据
        int k = 0;
        while(s1 <= e1 && s2 <= e2){
            if (arr[s1] <= arr[s2]){
                tmpArr[k++] = arr[s1++];
            }else{
                tmpArr[k++] = arr[s2++];
            }

        }
        //处理剩下的元素
        while(s1 <= e1){
            tmpArr[k++] = arr[s1++];

        }
        while(s2 <= e2){
            tmpArr[k++] = arr[s2++];

        }
        //把排好序的数据拷贝回原来的数组arr当中
        for (int i = 0; i < tmpArr.length; i++) {//要加上left对应顺序
            arr[i+left] = tmpArr[i];
        }

    }

    public static void mergeSortNor(int[] arr){
        int gap = 1;//每组有几个数据
        while(gap < arr.length){
            for (int i = 0; i < arr.length; i+=gap*2) {
                int left = i;
                int mid = left+gap-1;//可能会越界
                int right = mid + gap;//可能会越界
                if (mid >= arr.length){
                    mid = arr.length - 1;
                }
                if (right >= arr.length){
                    right = arr.length - 1;
                }

                merge(arr,left,mid,right);
            }

            gap *= 2;

        }
    }

    /**
     * 计数排序的场景: 指定范围内
     * 时间复杂度: O(Max(N,范围))
     * 空间复杂度: O(N)
     * @param arr
     */
    public static void countSort(int[] arr){
        //1. 申请一个数组
        int minVal = arr[0];
        int maxVal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < minVal){
                minVal = arr[i];
            }
            if (arr[i] > maxVal){
                maxVal = arr[i];
            }
        }
        int[] counts = new int[maxVal-minVal+1];
        //2. 遍历原来的数组,把数字对象对应的数组下标内容++
        for (int i = 0; i < arr.length; i++) {
            counts[arr[i]-minVal]++;
        }
        //3. 遍历计数数组,写回到原来数组,写的次数和元素值一样
        int j = 0;
        for (int i = 0; i < counts.length; i++) {

            while(counts[i] > 0){
                arr[j] = minVal+i;
                j++;
                counts[i]--;

            }
        }
    }


}
